package Offer.offer2020;

import java.util.Stack;

/**
 * 包含min函数的栈
 * min、push、pop的时间复杂度均为O（1）
 * 附加一个栈，每次放最小值
 * @Author: leiwenkang02
 * @Date: 2020/3/7 11:15 上午
 */
public class Test21 {

    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();

    public void push(int value) {
        stack1.push(value);
        if (!stack2.isEmpty() && stack2.peek() <= value) {
            stack2.push(stack2.peek());
        } else {
            stack2.push(value);
        }
    }

    public int pop() {
        if (stack1.isEmpty()) {
            throw new RuntimeException("为空");
        }
        stack2.pop();
        return stack1.pop();
    }

    public int min() {
        if (stack2.isEmpty()) {
            throw new RuntimeException("为空");
        }
        return stack2.peek();
    }

}
